/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/binary-search-tree-iterator
   @Language: C++
   @Datetime: 19-11-27 17:37
   */

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class BSTIterator {
	stack<TreeNode*> nodes;
	void prepare(TreeNode *root){
		for(; root; root=root->left)
			nodes.push(root);
	}
public:
	BSTIterator(TreeNode* root) {
		for(; nodes.size(); nodes.pop());
		prepare(root);
	}

	/** @return the next smallest number */
	int next() {
		if(nodes.size()==0) return 0;
		TreeNode *node=nodes.top();
		nodes.pop();
		prepare(node->right);
		return node->val;
	}

	/** @return whether we have a next smallest number */
	bool hasNext() {
		return nodes.size();
	}
};

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator* obj = new BSTIterator(root);
 * int param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */
